Lagrange 对偶

#Dual #KKT #SlaterCondition #AffineFunction #LagrangeMethod

Lagrange 对偶是优化损失函数中的重要方法, 在很多时候它将原始问题转换为等价的对偶问题. 对偶后的问题可能有凸性 (容易找到全局最优解)、降维、简化等优点.

1 原始问题

设 $f (x), c_{i} (x), h_{j} (x)$ 是 $R^{n}$ 上的连续可微函数. 一般的最优化问题写为 $\begin{aligned} min_{x \in R^{n}} & f (x) \\ s . t . & c_{i} (x) \leq 0, i = 1, \dots, k, \\ (1.1) & h_{j} (x) = 0, j = 1, \dots, l . \end{aligned}$
定义广义 Lagrange 函数 (generalized Lagrange function): $\begin{matrix} (1.2) & L (x, α, β) = f (x) + \sum_{i = 1}^{k} α_{i} c_{i} (x) + \sum_{j = 1}^{l} β_{j} h_{j} (x) . \end{matrix}$
这里 $x = (x^{(1)}, \dots, x^{(n)})^{T} \in R^{n}$ , $α_{i}, β_{j}$ 是 Lagrange 乘子, $α_{i} \geq 0$ . 定义 $θ_{P} (x) = max_{α, β : α_{i} \geq 0} L (x, α, β) .$
(用 $P$ 表示原始问题)

命题

极小化问题 $\begin{matrix} (1.3) & min_{x} θ_{P} (x) = min_{x} max_{α, β : α_{i} \geq 0} L (x, α, β) \end{matrix}$ 与 (1.1) 等价. 将它称为广义 Lagrange 函数的 极小极大问题.

证明

给定 $x$ , 若它违反原始问题 (1.1) 的约束条件, 也即存在 $i$ 使得 $c_{i} (x) > 0$ 或存在 $j$ 使得 $h_{j} (x) \neq 0$ , 则 $θ_{P} (x) = max_{α, β : α_{i} \geq 0} [f (x) + \sum_{i = 1}^{k} α_{i} c_{i} (x) + \sum_{j = 1}^{l} β_{j} h_{j} (x)] = + \infty .$
而如果 $x$ 符合约束条件, 则 $θ_{P} (x) = max_{α : α_{i} \geq 0} f (x) + \sum_{i = 1}^{k} α_{i} c_{i} (x) + 0 = f (x),$ 因此 $θ_{P} (x)$ 只有 $f (x)$ 和 $+ \infty$ 两种可能, 从而 (1.3), (1.1) 等价.

2 对偶问题

定义 $\begin{matrix} (1.4) & θ_{D} (α, β) = min_{x} L (x, α, β), \end{matrix}$

对偶问题

定义原始问题的 对偶问题 为 $\begin{aligned} max_{α, β : α_{i} \geq 0} θ_{D} (α, β) & = max_{α, β : α_{i} \geq 0} min_{x} L (x, α, β) . \\ (1.5) & s . t . & α_{i} \geq 0, i = 1, \dots, k . \end{aligned}$
(称为极大极小问题), 而对偶问题的值为 $d^{*} = max_{α, β : α_{i} \geq 0} θ_{D} (α, β) .$

下面探讨原始问题与对偶问题的关系.

定理 1

若两问题都有最优值, 则 $d^{*} = max_{α, β : α_{i} \geq 0} min_{x} L (x, α, β) \leq min_{x} max_{α, β : α_{i} \geq 0} L (x, α, β) = p^{*} .$

证明

显然 $θ_{D} (α, β) = min_{x} L (x, α, β) \leq L (x, α, β) \leq max_{α, β : α_{i} \geq 0} L (x, α, β) = θ_{P} (x),$ 从而 $θ_{D} (α, β) \leq θ_{P} (x)$ . 由于两问题都有最优值, 也即 $θ_{P}, θ_{D}$ 的最值存在, 而两个 $θ$ 分别由 $α, β$ 和 $x$ 决定, 互不影响, 因此 $max_{α, β : α_{i} \geq 0} θ_{D} (α, β) \leq min_{x} θ_{P} (x),$ 这样就完成了证明.

推论

如果上述定理的 $d^{*} = p^{*}$ , 且两问题都有一组可行解 $x^{*}, α^{*}, β^{*}$ , 则这是两个问题共同的最优解.

定理 2

如果 $f (x), c_{i} (x)$ 是凸函数, $h_{j} (x)$ 是仿射函数^[1], $c_{i} (x)$ 的约束严格可行( $\exists x, \forall i : c_{i} (x) < 0$ ), 则存在原始问题的解 $x^{*}$ 和对偶问题的解 $α^{*}, β^{*}$ , 且 $p^{*} = d^{*} = L (x^{*}, α^{*}, β^{*}) .$

这里的条件被称为Slater 条件.

定理 3 (KKT 条件)

条件同定理 2. 则 $x^{*}, α^{*}, β^{*}$ 分别是两个问题解的充分必要条件是 $\begin{aligned} \nabla_{x} L (x^{*}, α^{*}, β^{*}) = 0, \\ (对偶互补条件) & α_{i}^{*} c_{i} (x^{*}) = 0, & i = 1, \dots, k, \\ c_{i} (x^{*}) \leq 0, & i = 1, \dots, k, \\ α_{i}^{*} \geq 0, & i = 1, \dots, k, \\ h_{j} (x^{*}) = 0, & j = 1, \dots, l . \end{aligned}$

对偶互补条件告诉我们如果 $α_{i}^{*} > 0$ , 则 $c_{i} (x^{*}) = 0$ .

例子

解如下问题: $\begin{aligned} min & x_{1}^{2} + x_{2}^{2} \\ s . t . & x_{1} + x_{2} = 1, \\ x_{2} \leq α . \end{aligned}$ 定义 Lagrange 函数 $L (x_{1}, x_{2}, λ, μ) = x_{1}^{2} + x_{2}^{2} + λ (1 - x_{1} - x_{2}) + μ (x_{2} - α),$ 则 KKT 条件为 $\begin{array}{r} {\begin{aligned} \partial_{x_{1}} L = 2 x_{1} - λ = 0, \\ \partial_{x_{2}} L = 2 x_{2} - λ + μ = 0, \\ x_{1} + x_{2} = 1, \\ x_{2} - α \leq 0, \\ μ \geq 0, \\ μ (x_{2} - α) = 0. \end{aligned} \end{array}$ 解得 $x_{1} = \frac{μ}{4} + \frac{1}{2}, x_{2} = - \frac{μ}{4} + \frac{1}{2}, - \frac{μ}{4} + \frac{1}{2} \leq α .$

若 $α > \frac{1}{2}, μ = 0$ , 则 $x_{1}^{*} = x_{2}^{*} = \frac{1}{2}$ , 极小值为 $\frac{1}{2}$ ;
若 $α = \frac{1}{2}, μ = 0$ , 同上;
若 $α < \frac{1}{2}, μ = 2 - 4 α$ , 则 $x_{1}^{*} = 1 - α, x_{2}^{*} = α$ , 极小值为 $(1 - α)^{2} + α^{2}$ .

仿射函数(Affine function): 向量值函数形如 $f (x) = A x + b$ . ↩︎